|
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the ''n'' entries in the tuple such that either : modulo ''n'', for all entries ''i = 1, ..., n'', or : modulo ''n'', for all entries ''i = 1, ..., n''. The result of repeatedly applying circular shifts to a given tuple are also called the circular shifts of the tuple. For example, repeatedly applying circular shifts to the four-tuple (''a'', ''b'', ''c'', ''d'') successively gives * (''d'', ''a'', ''b'', ''c''), * (''c'', ''d'', ''a'', ''b''), * (''b'', ''c'', ''d'', ''a''), * (''a'', ''b'', ''c'', ''d'') (the original four-tuple), and then the sequence repeats; this four-tuple therefore has four distinct circular shifts. However, not all ''n''-tuples have ''n'' distinct circular shifts. For instance, the 4-tuple (''a'', ''b'', ''a'', ''b'') only has 2 distinct circular shifts. In general the number of circular shifts of an ''n''-tuple could be any divisor of ''n'', depending on the entries of the tuple. In computer programming, a circular shift (or bitwise rotation) is a shift operator that shifts all bits of its operand. Unlike an arithmetic shift, a circular shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa. Unlike a logical shift, the vacant bit positions are not filled in with zeros but are filled in with the bits that are shifted out of the sequence. == Implementing circular shifts == Circular shifts are used often in cryptography in order to permute bit sequences. Unfortunately, many programming languages, including C, do not have operators or standard functions for circular shifting, even though virtually all processors have bitwise operation instructions for it (e.g. Intel x86 has ROL and ROR). However, some compilers may provide access to the processor instructions by means of intrinsic functions. In addition, it is possible to write standard ANSI C code that compiles down to the "rotate" assembly language instruction (on CPUs that have such an instruction). Most C compilers recognize the following idiom, and compile it to a single 32-bit rotate instruction.〔 (GCC: "Optimize common rotate constructs" ) 〕〔 ("Cleanups in ROTL/ROTR DAG combiner code" ) mentions that this code supports the "rotate" instruction in the CellSPU 〕 / * * Shift operations in C are only defined for shift values which are * not negative and smaller than sizeof(value) * CHAR_BIT. * The mask, used with bitwise-and (&), prevents undefined behaviour * when the shift count is 0 or >= the width of unsigned int. */ #include #include uint32_t rotl32 (uint32_t value, unsigned int count) uint32_t rotr32 (uint32_t value, unsigned int count) This safe and compiler-friendly implementation was developed by John Regehr,〔(Safe, Efficient, and Portable Rotate in C/C++ )〕 and further polished by Peter Cordes〔(Stackoverflow: Best practices for rotates in C/C++ )〕〔(Near constant time rotate that does not violate the standards )〕 For C++, the use of templates can expand the support to all integer types: template #if __cplusplus > 201100L // Apply constexpr to C++ 11 to ease optimization constexpr #endif // See also http://stackoverflow.com/a/7269693/3770260 INT rol(INT val, size_t len) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「circular shift」の詳細全文を読む スポンサード リンク
|